package P659_分割数组为连续子序列;

import java.util.HashMap;
import java.util.SortedMap;
import java.util.TreeMap;


public class Solution {
    //贪心算法,每次从retMap中找以k结尾的序列，把他加长，如果找不到，那么生成新的，并且是k,k+1,k+2序列
    //更新retMap，然后继续，如果生成不了，就返回false
    public boolean isPossible(int[] nums) {
        //数与个数
        SortedMap<Integer, Integer> map = new TreeMap<>();
        //以key结尾的子序列的个数(子序列起码包含3个数，是一个符合题意的序列）
        HashMap<Integer, Integer> retMap = new HashMap<>();
        for(int i : nums){
            map.put(i, map.getOrDefault(i,0) + 1);
        }
        int k;
        for(int i = 0; i< nums.length;i++){
            k = nums[i];
            if(map.get(k) == 0){
                //如果map中都没有了，证明被消耗过了，直接continue
                continue;
            }
            if(retMap.getOrDefault(k - 1, 0) > 0){
                //把它直接加长
                retMap.put(k - 1, retMap.get(k - 1) - 1);
                retMap.put(k, retMap.getOrDefault(k, 0) + 1);
                map.put(k, map.get(k) - 1);
            }else{
                if(map.getOrDefault(k + 1,0) > 0 && map.getOrDefault(k + 2, 0) > 0){
                    //如果后面两个数都有，那么生成新的链表
                    map.put(k, map.get(k) - 1);
                    map.put(k + 1, map.get(k + 1) - 1);
                    map.put(k + 2, map.get(k + 2) - 1);
                    retMap.put(k + 2, retMap.getOrDefault(k + 2, 0) + 1);
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args){
        System.out.println(new Solution().isPossible(new int[]{1,2,3,4,4,5}));
    }
}
